home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / ddj9304.zip / 1993-APR.ZIP / FRAG.ASC < prev    next >
Text File  |  1993-02-17  |  16KB  |  683 lines
  1. _MEASURING FRAGMENTATION_
  2. by James Harrington
  3.  
  4. [LISTING ONE]
  5.  
  6. /* This module contains a generic function that calculates a fragmen-
  7.     tation index. This index depends on the numbers of used and free
  8.     block, the largest number of bytes that can currently be allocated
  9.     in a contiguous block, and the total amount of free memory.
  10.  
  11.     Several functions declared as "extern" will be found in other
  12.     modules, where each module calculates values as appropriate for
  13.     a particular memory manager.
  14. */
  15.  
  16. #include <stdio.h>
  17.  
  18. double fragindex( void );
  19. double getHeapSizeF( void );
  20. double getBreakupF( void );
  21. double getLargeFreeF( void );
  22. double getWorstCase( void );
  23.  
  24. extern double getWorstCase( void );    /* In manager-specific module */
  25. extern long getnfreeblks( void );   /* In manager-specific module */
  26. extern long getnusedblks( void );   /* In manager-specific module */
  27. extern long getlargest( void );     /* In manager-specific module */
  28. extern long gettotalfree( void );
  29.  
  30. /*********************************************************************
  31. *
  32. * double fragindex( void )
  33. *
  34. * This procedure returns a relative value that reflects the degree of
  35. * heap fragmentation. It is calculated as follows:
  36. *
  37. *        frag_index = BreakupFactor / LargeFreeFactor
  38. *
  39. *        BreakupFactor = number of free blocks-1 / number of used
  40. *            blocks+1, where the free memory above utilized heap is
  41. *            counted as a free block.
  42. *        LargeFreeFactor = size of largest block that can be success-
  43. *            fully allocated / total amount of unused memory,
  44. *            including overhead.
  45. *
  46. * maximal fragmentation occurs when every other block is free, all
  47. * blocks are of the minimal size, and all of memory has been filled
  48. * with used:free block pairs.
  49. *
  50. * If adjacent free blocks are allowed to exist, maximal fragmentation
  51. * occurs when every block is free (except perhaps for one, and not
  52. * counting any blocks allocated by startup code), all blocks are of
  53. * the minimal size, and all of memory has been filled with free
  54. * blocks.
  55. *
  56. * Returns -1 in case of error condition - corrupt heap or setdos()
  57. * not called in an MSC program. setdos() is required only if compar-
  58. * ing with other memory managers.
  59. *
  60. *********************************************************************/
  61.  
  62. double fragindex( void )
  63. {
  64.     double breakupF, largeFreeF;
  65.  
  66.     breakupF = getBreakupF();
  67.     largeFreeF = getLargeFreeF();
  68.  
  69.     if( breakupF<0 || largeFreeF<0 )
  70.         return( -1 );
  71.  
  72.     if( !largeFreeF )
  73.         return( 0 );
  74.     else
  75.         return ( breakupF/largeFreeF );
  76. }
  77.  
  78. /*********************************************************************
  79. *
  80. * getBreakupF
  81. *
  82. * Returns the BreakupFactor for use in the fragindex function.
  83. *
  84. *********************************************************************/
  85.  
  86. double getBreakupF( void )
  87. {
  88.     long nfree, nused;
  89.  
  90.     nfree = getnfreeblks();
  91.     nused = getnusedblks();
  92.  
  93.     if( nfree<=0 )
  94.         return(nfree);
  95.  
  96.     return (double)(--nfree) / (double)(++nused);
  97. }
  98.  
  99. /*********************************************************************
  100. *
  101. * getLargeFreeF
  102. *
  103. * Returns the LargeFreeFactor for use in the fragindex function.
  104. *
  105. * Returns -1 if error in heapwalk, 0 if is no free memory
  106. *
  107. *********************************************************************/
  108.  
  109. double getLargeFreeF( void )
  110. {
  111.     double sizelargest;
  112.  
  113.     sizelargest = (double)getlargest();
  114.  
  115.     if( sizelargest < 0 )
  116.         return( -1 );
  117.  
  118.     if( !sizelargest )
  119.         return( 0 );
  120.     else
  121.         return (sizelargest / (double)gettotalfree());
  122. }
  123.  
  124.  
  125. [LISTING TWO]
  126.  
  127. /* Provides Borland-specific versions of functions called by fragindex() */
  128.  
  129. /* Assumes no UMBs, etc., are available to malloc() */
  130.  
  131. #include <alloc.h>
  132. #include <stdlib.h>
  133. #include <stdio.h>
  134.  
  135. long gettotalfree( void );
  136. long getnusedblks( void );
  137. long getnfreeblks( void );
  138. long getlargest( void );
  139. void setdos( void );
  140.  
  141. /*********************************************************************
  142. *
  143. * getlargest( void );
  144. *
  145. * Returns a number of bytes, the size of the largest block of
  146. * contiguous free memory that can be successfully allocated from the
  147. * heap with farmalloc(), malloc(), or _halloc().
  148. *
  149. *********************************************************************/
  150.  
  151. long getlargest( void )
  152. {
  153.     struct farheapinfo hinfo;
  154.     long size = 0;
  155.  
  156.     hinfo.ptr = NULL;
  157.  
  158.     while( heapwalk( &hinfo ) == _HEAPOK ){
  159.  
  160.         if( !hinfo.in_use )
  161.             size = max( size, hinfo.size );
  162.     }
  163.  
  164.     size = max( size, farcoreleft()-4 );
  165.  
  166.     return( size );
  167. }
  168.  
  169. /*********************************************************************
  170. *
  171. * getnfreeblks( void );
  172. *
  173. * Returns the number of free blocks in the heap. Doesn't count memory
  174. * above utilized heap.
  175. *
  176. * Returns -1 if heap is corrupt
  177. *
  178. *********************************************************************/
  179.  
  180. long getnfreeblks( void )
  181. {
  182.     struct farheapinfo hinfo;
  183.     register int count = 0;
  184.  
  185.     if( heapcheck() < 0 )
  186.         return( -1 );
  187.  
  188.     hinfo.ptr = NULL;
  189.  
  190.     while( heapwalk( &hinfo ) == _HEAPOK ){
  191.  
  192.         if( !hinfo.in_use )
  193.             count++;
  194.     }
  195.     /* ret count+1 to count coreleft() memory */
  196.     return (long) ++count;
  197. }
  198.  
  199. /*********************************************************************
  200. *
  201. * getnusedblks( void );
  202. *
  203. * Returns the number of allocated blocks in the heap.
  204. *
  205. *********************************************************************/
  206.  
  207. long getnusedblks( void )
  208. {
  209.     struct farheapinfo hinfo;
  210.     register int count = 0;
  211.  
  212.     hinfo.ptr = NULL;
  213.  
  214.     while( heapwalk( &hinfo ) == _HEAPOK ){
  215.  
  216.         if( hinfo.in_use )
  217.             count++;
  218.     }
  219.  
  220.     return (long) count;
  221. }
  222.  
  223. /*********************************************************************
  224. *
  225. * gettotalfree( void );
  226. *
  227. * Returns the total amount of free memory.
  228. *
  229. *********************************************************************/
  230.  
  231. long gettotalfree( void )
  232. {
  233.     struct farheapinfo hinfo;
  234.     long size=0;
  235.  
  236.     hinfo.ptr = NULL;
  237.  
  238.     while( heapwalk( &hinfo ) != _HEAPEND ){
  239.  
  240.         if( !hinfo.in_use )
  241.             size+=(hinfo.size+4);
  242.     }
  243.     size += farcoreleft();
  244.  
  245.     return (long)size;
  246. }
  247.  
  248.  
  249. /*********************************************************************
  250. *
  251. * setdos( void );
  252. *
  253. * For sake of compatibility with fragmic.c
  254. *
  255. *********************************************************************/
  256.  
  257. void setdos( void )
  258. {
  259. }
  260.  
  261.  
  262.  
  263. [LISTING THREE]
  264.  
  265. /* Provides Microsoft C-specific versions of functions used in
  266.     calculating a fragmentation index.                                 */
  267.  
  268. /* Assumes no UMBs, etc., are available to malloc() */
  269.  
  270. #include <malloc.h>
  271. #include <stdlib.h>
  272. #include <stdio.h>
  273. #include <dos.h>
  274.  
  275. #define LOWSEGS 100
  276.         /* signed int, must be > 0 */
  277.         /* represents the max number of
  278.            free DOS blocks expected at
  279.            time of program startup */
  280. #define NDOS 200
  281.         /* signed int, must be > 0 */
  282.         /* affected by value of
  283.            _amblksize variable - smaller
  284.            val means larger NDOS req'd */
  285.         /* represents max number of
  286.            free DOS blocks
  287.            expected                */
  288.  
  289. int nsegs, _callflag;
  290. unsigned _far dosseg_array[ LOWSEGS ]; /* saves segs for findfrag() */
  291. unsigned _far seg_array[ NDOS ];       /* saves segs for setdos()   */
  292.  
  293. void limitheap( void );
  294. void freesegs( void );
  295. long countdos( void );
  296. long bigdos( void );
  297. long dossize( void );
  298. long gettotalfree( void );
  299. long getnusedblks( void );
  300. long getnfreeblks( void );
  301. long getlargest( void );
  302. void setdos( void );
  303. void freedos( int count );
  304.  
  305. /* Note: _dos_allocmem() is a compiler runtime library function that
  306.     allocates a block of memory directly from MS-DOS through int 21h
  307.     fxn. 48h. You request a number of paragraphs (blocks of 16 bytes).
  308.     Requesting 0xffff paragraphs will result in an error return, with
  309.     the size of the largest allocable block, in paragraphs, being
  310.     returned in the variable whose address is passed as the second
  311.     parameter to _dos_allocmem(). _dos_freemem() frees the blocks
  312.     allocated through _dos_allocmem(), via int 21h fxn 49h.
  313. */
  314.  
  315. /*********************************************************************
  316. *
  317. * getlargest( void );
  318. *
  319. * Returns a number of bytes, the size of the largest block of contigu-
  320. * ous free memory that can be successfully allocated from the heap
  321. * with fmalloc(), malloc() (in far data memory models), or _halloc().
  322. *
  323. * Returns -1 if error
  324. *
  325. *********************************************************************/
  326.  
  327. long getlargest( void )
  328. {
  329.     struct _heapinfo hinfo;
  330.     int herr;
  331.     long maxsize = 0;
  332.     long tsize = 0;
  333.     char first = 0;
  334.     unsigned seg = 0;
  335.  
  336.     maxsize = bigdos();
  337.  
  338.     /* Get largest free */
  339.  
  340.     hinfo._pentry = NULL;
  341.  
  342.     while( (herr=_heapwalk( &hinfo )) != _HEAPEND && herr==_HEAPOK){
  343.  
  344.         /* if is a used block... */
  345.         if( hinfo._useflag ){
  346.  
  347.             first = 0;
  348.  
  349.             seg = (unsigned)(((unsigned long)hinfo._pentry)>>16);
  350.         }
  351.  
  352.         /* but if is a free block... */
  353.         else{
  354.  
  355.             /* if last block was a used block */
  356.             if( !first ){
  357.  
  358.                 tsize = hinfo._size;
  359.  
  360.                 /* If switch DOS blocks */
  361.                 if( (unsigned)(((unsigned long)hinfo._pentry)>>16)
  362.                                                             != seg )
  363.                     seg =
  364.                        (unsigned)(((unsigned long)hinfo._pentry)>>16);
  365.  
  366.                 maxsize = max( maxsize, tsize );
  367.  
  368.                 first=1;
  369.             }
  370.  
  371.             /* if last block was a free block too */
  372.             else{
  373.  
  374.                 /* If switch DOS blocks */
  375.                 if( (unsigned)(((unsigned long)hinfo._pentry)>>16)
  376.                                                          != seg ) {
  377.                     seg =
  378.                       (unsigned)(((unsigned long)hinfo._pentry)>>16);
  379.                     tsize = hinfo._size;
  380.                 }
  381.                 else
  382.                     tsize += (hinfo._size+2);
  383.  
  384.                 maxsize = max( maxsize, tsize );
  385.             }
  386.         }
  387.     }
  388.  
  389.     return( herr==_HEAPEND?maxsize:-1 );
  390. }
  391.  
  392. /*********************************************************************
  393. *
  394. * long bigdos( void )
  395. *
  396. * Returns the size of the largest block of available DOS memory.
  397. *
  398. *********************************************************************/
  399.  
  400. long bigdos( void )
  401. {
  402.     unsigned size;
  403.  
  404.     _dos_allocmem( 0xffff, &size );
  405.  
  406.     return( (long)(size-1) * 16L );    /* Size of largest allocable
  407.                                                             block */
  408. }
  409.  
  410.  
  411. /*********************************************************************
  412. *
  413. * getnfreeblks( void );
  414. *
  415. * Returns the number of free blocks in the heap, and assumes adjacent
  416. * free blocks in the same DOS block can be combined.
  417. *
  418. * Returns -1 in case of error
  419. *
  420. *********************************************************************/
  421.  
  422. long getnfreeblks( void )
  423. {
  424.     struct _heapinfo hinfo;
  425.     int herr;
  426.     unsigned seg;
  427.     long count = 0;
  428.     char first = 0;
  429.  
  430.     /* error if didn't call setdos() */
  431.     if( !_callflag )
  432.         return( -1 );
  433.  
  434.     hinfo._pentry = NULL;
  435.  
  436.     while( (herr=_heapwalk( &hinfo )) != _HEAPEND && herr==_HEAPOK){
  437.  
  438.         /* if is a used block... */
  439.         if( hinfo._useflag ){
  440.  
  441.             first = 0;
  442.  
  443.             seg = (unsigned)(((unsigned long)hinfo._pentry)>>16);
  444.         }
  445.  
  446.         /* but if is a free block... */
  447.         else{
  448.  
  449.             /* if last block was a used block */
  450.             if( !first ){
  451.  
  452.                 count++;
  453.  
  454.                 /* If switch DOS blocks */
  455.                 if( (unsigned)(((unsigned long)hinfo._pentry)>>16)
  456.                                                              != seg )
  457.                     seg =
  458.                      (unsigned)(((unsigned long)hinfo._pentry)>>16);
  459.             }
  460.  
  461.             /* if last block was a free block too */
  462.             else{
  463.  
  464.                 /* If switch DOS blocks */
  465.                 if( (unsigned)(((unsigned long)hinfo._pentry)>>16)
  466.                                                              != seg ){
  467.                     seg =
  468.                        (unsigned)(((unsigned long)hinfo._pentry)>>16);
  469.                     count++;
  470.                 }
  471.             }
  472.         }
  473.     }
  474.  
  475.     return( herr==_HEAPEND?(count+countdos()):-1 );
  476. }
  477.  
  478. /*********************************************************************
  479. *
  480. * int countdos( void )
  481. *
  482. * Counts the number of free DOS blocks, up to NDOS blocks
  483. *
  484. *********************************************************************/
  485.  
  486. long countdos( void )
  487. {
  488.     int count;
  489.  
  490.     for( count=0; count<NDOS; count++ ){
  491.  
  492.         _dos_allocmem( 0xffff, &seg_array[count] );
  493.  
  494.         if( seg_array[count] )
  495.             _dos_allocmem( seg_array[count], &seg_array[count] );
  496.         else
  497.             break;
  498.     }
  499.  
  500.     /* count is the number of allocated blocks */
  501.  
  502.     freedos(count);
  503.  
  504.     if( count == NDOS ){
  505.         printf("\nToo many DOS blocks; increase value of NDOS.");
  506.         exit(0);
  507.     }
  508.  
  509.     return count;
  510. }
  511.  
  512. /*********************************************************************
  513. *
  514. * getnusedblks( void );
  515. *
  516. * Returns the number of allocated blocks in the heap.
  517. *
  518. *********************************************************************/
  519.  
  520. long getnusedblks( void )
  521. {
  522.     struct _heapinfo hinfo;
  523.     long count = 0;
  524.  
  525.     hinfo._pentry = NULL;
  526.  
  527.     while( _heapwalk( &hinfo ) != _HEAPEND ){
  528.  
  529.         if( hinfo._useflag )
  530.             count++;
  531.     }
  532.     return count;
  533. }
  534.  
  535. /*********************************************************************
  536. *
  537. * gettotalfree( void );
  538. *
  539. * Returns the total amount of free memory.
  540. *
  541. *********************************************************************/
  542.  
  543. long gettotalfree( void )
  544. {
  545.     struct _heapinfo hinfo;
  546.     long size=0;
  547.  
  548.     hinfo._pentry = NULL;
  549.  
  550.     while( _heapwalk( &hinfo ) != _HEAPEND ){
  551.  
  552.         if( !hinfo._useflag )
  553.             size+=(hinfo._size+2);
  554.     }
  555.     return size + dossize();
  556. }
  557.  
  558. /*********************************************************************
  559. *
  560. * dossize( void )
  561. *
  562. * Counts the number of bytes in free DOS blocks, up to NDOS DOS
  563. * blocks. Includes 16 bytes overhead for each block.
  564. *
  565. *********************************************************************/
  566. long dossize( void )
  567. {
  568.     unsigned seg_array[NDOS];
  569.     int count;
  570.     long size = 0;
  571.  
  572.     for( count=0; count<NDOS; count++ ){
  573.  
  574.         _dos_allocmem( 0xffff, &seg_array[count] );
  575.  
  576.         if( seg_array[count] ){
  577.             size += ((long)seg_array[count]+1)*16L;
  578.             _dos_allocmem( seg_array[count], &seg_array[count] );
  579.         }
  580.         else
  581.             break;
  582.     }
  583.  
  584.     /* count is the number of allocated blocks */
  585.  
  586.     freedos(count);
  587.  
  588.     if( count == NDOS ){
  589.         printf("\nToo many DOS blocks; increase value of NDOS.");
  590.         exit(0);
  591.     }
  592.  
  593.     return( size );
  594. }
  595.  
  596. /*********************************************************************
  597. *
  598. * void freedos( int count )
  599. *
  600. * Frees segments stored in seg_array[].
  601. *
  602. * Parm "count" is number of stored segments.
  603. *
  604. *********************************************************************/
  605.  
  606. void freedos( int count )
  607. {
  608.     int i;
  609.  
  610.     if( !count )
  611.         return;
  612.  
  613.     for( i=0; i<count; i++ )
  614.         _dos_freemem( seg_array[i] );
  615. }
  616.  
  617. /*********************************************************************
  618. *
  619. * setdos( void );
  620. *
  621. *********************************************************************/
  622.  
  623. void setdos( void )
  624. {
  625.     atexit( freesegs );
  626.     limitheap();
  627.     _callflag++;
  628. }
  629.  
  630. /*********************************************************************
  631. *
  632. * limitheap()
  633. *
  634. * This function allocates all the DOS blocks besides the one
  635. * immediately above the program block. Assumes that the one above the
  636. * program block is the biggest free DOS block.
  637. *
  638. *********************************************************************/
  639. void limitheap(void)
  640. {
  641.     /* nsegs = 0 at start */
  642.  
  643.     while( nsegs<LOWSEGS ){
  644.  
  645.         _dos_allocmem( 0xffff, &dosseg_array[nsegs] );
  646.  
  647.         if( dosseg_array[nsegs] ){
  648.             _dos_allocmem( dosseg_array[nsegs],&dosseg_array[nsegs] );
  649.             nsegs++;
  650.         }
  651.         else
  652.             break;
  653.     }
  654.  
  655.     if( nsegs == LOWSEGS ){
  656.  
  657.         _dos_freemem( dosseg_array[0] );
  658.  
  659.         printf("\nToo many free DOS blocks at start; ");
  660.         printf("\nincrease value of of LOWSEGS.");
  661.         exit(0);
  662.     }
  663.  
  664.     if( nsegs )
  665.         _dos_freemem( dosseg_array[0] );
  666. }
  667.  
  668. void freesegs(void)
  669. {
  670.     int i;
  671.  
  672.     if( !_callflag )
  673.         printf("\nerror: didn't call setdos()");
  674.     else{
  675.         if( nsegs>1 ){
  676.  
  677.             for( i=1; i<nsegs; i++ )
  678.                 _dos_freemem( dosseg_array[i] );
  679.         }
  680.     }
  681. }
  682.  
  683.